Article Outline
由一个很长的二进制向量和一系列随机映射函数组成。布隆过滤器可用于检索一个元素是否在一个集合里
基本概念
布隆过滤器可用于检索一个元素是否在一个集合里，一般可将所有元素保存起来然后通过比较确定。但随着元素的增加，存储空间增加，检索速度变慢。链表、树等数据结构都是这种思路。而利用哈希表的数据结构，可通过一个Hash函数将一个元素映射成一个位阵列中的一个点，只需要观察这个点是否为1即可知晓集合中是否存在该元素，也就是布隆过滤器的基本思想
Hash冲突
Hash冲突指参数不同但是通过Hash函数计算得出的结果相同。如果Hash函数设计良好，位阵列长度是m个点，那如果想将冲突率降低至1%，散列表就只能容纳m/100个元素，显然无法有效利用空间解决方案 使用多个Hash。如果其中一个Hash否认了元素在集合中，那么集合中肯定不存在该元素；如果所有Hash都确认了元素在集合中这一事实，虽然有一定概率是误判，但概率较低
优点
- 存储空间和查询/插入时间都是 O(n)，在时间和空间方面都具备巨大优势
- Hash函数之间无关联，可并行执行
- 不需要存储元素，适用于某些保密要求严格的场合
- 仅有布隆过滤器这种数据结构可标识全集
- 位阵列数组的大小 m 和 Hash函数的个数 k 相同时，使用同组Hash函数的两个布隆过滤器的交并差运算可通过位操作进行
缺点
- 误判率。误判率会随着存入元素的数量增加而增加
- 不能从布隆过滤器中删除元素。为了安全地删除元素，必须保证删除的元素确实存在于布隆过滤器中，然而布隆过滤器无法保证这一点。如果把位阵列转化为整型数组，每插入一个元素相应的计数器+1，删除元素时-1，然而计数器回绕可能也会造成问题